package cg.studio.algorithm.permutation;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.SortedMap;

public class RecursivePermutator implements Permutator
{
  public List< char[] > permutate( String str )
  {
    SortedMap< Character, Integer > charToCountMap = PermutationUtils.getCharToCountMap( str );
    if( charToCountMap == null || charToCountMap.isEmpty() )
      return Collections.emptyList();
    
    List< char[] > permutation = new ArrayList< char[] >();
    List<Character> permutatedChars = new ArrayList<Character>();
    
    permutate( permutatedChars, charToCountMap, permutation );
    return permutation;
  }
  
  /**
   * 
   * @param permutatedChars - the leading chars which have been permutated
   * @param charToCountMap  - the remain chars which need to be permutated
   * @param permutation     - the list which keeps the permutation
   */
  protected void permutate( List<Character> permutatedChars, SortedMap< Character, Integer > charToCountMap, List< char[] > permutation )
  {
    if( charToCountMap.isEmpty() )
    {
      copyAndAddOneRow( permutation, permutatedChars );
      return;
    }
    
//    Set< Character > keys = charToCountMap.keySet();  //concurrent issue.
    Character[] keys = charToCountMap.keySet().toArray( new Character[0] );
//    List<Character> ClonedPermutatedChars = new ArrayList<Character>( permutatedChars );
    int permutatedCharSize = permutatedChars.size();
    for( int index=0; index<keys.length; ++index )
    {
      Character theKey = keys[index];
      //for same key(even if it has multiple count), only add to permutatedChars once
      permutatedChars.add( theKey );
      permutate( permutatedChars, PermutationUtils.decreaseCharCount( charToCountMap, theKey ), permutation );

      //the previous key should already handled and copy and add to the permutation.
      //so, recover the environment for next loop
      PermutationUtils.increaseCharCount( charToCountMap, theKey );
      permutatedChars = permutatedChars.subList( 0, permutatedCharSize );
    }
  }

  protected void copyAndAddOneRow( List< char[] > permutation, List<Character> permutatedChars )
  {
    char[] row = new char[ permutatedChars.size() ];
    int column = 0;
    for( Character theChar : permutatedChars )
    {
      row[ column++ ] = theChar;
    }
    permutation.add( row );
  }
  
  /**
   * This function only print all possible permutation, but don't allocate memory to keep them
   * The input chars could be duplicated.
   * basic steps
   *   - sort input chars
   *   - move one char( curChar ) to prefix, 
   *     - if curChar equals to the previous char, which mean the permutation on this char already done, don't recursive
   *     - else, recursive on this char  
   * @param chars
   */
  public void printPermutation( char[] chars )
  {
    if( chars == null || chars.length == 0 )
      return;
    Arrays.sort( chars );
    printPermutation( new StringBuilder(), chars );
  }
  
  public void printPermutationWithArray( char[] chars )
  {
    if( chars == null || chars.length == 0 )
      return;
    Arrays.sort( chars );
    printPermutation( new char[ chars.length ], 0, chars );
  }
  
  /**
   * use string as prefix
   * precondition: the chars are sorted
   * @param prefix
   * @param chars
   */
  protected void printPermutation( StringBuilder prefix, char[] chars )
  {
    int count = 0;
    char preChar = 0;
    for( int i=0; i<chars.length; ++i )
    {
      char curChar = chars[i];
      if( curChar == 0 )
        continue;
      ++count;
      
      //if current char duplicate with previous one, no recursive required
      if( preChar == curChar )
        continue;
      
      //only recursive when curChar equals to the preChar
      //erase from chars and move to prefix for next recursive;
      chars[i] = 0;  
      prefix.append(curChar );
      
      if( curChar != preChar )    
        printPermutation( prefix, chars );
      
      //restore the environment after recursive and prepare for next loop;
      chars[i] = curChar;  
      prefix.deleteCharAt( prefix.length()-1 );

      preChar = curChar;      
    }
    if( count == 0 )
      System.out.println( prefix );
  }
  
  /**
   * try use char array as prefix`
   * precondition: the chars are sorted
   * @param prefix
   * @param chars
   */
  protected void printPermutation( char[] prefix, int prefixLen, char[] chars )
  {
    if( prefixLen == chars.length )
    {
      print( prefix, prefixLen );
      return;
    }
    
    char preChar = 0;
    for( int i=0; i<chars.length; ++i )
    {
      char curChar = chars[i];
      if( curChar == 0 )
        continue;
      
      //if current char duplicate with previous one, no recursive required
      if( preChar == curChar )
        continue;
      
      //erase from chars and move to prefix for next recursive;
      chars[i] = 0;  
      prefix[ prefixLen ] = curChar;
      printPermutation( prefix, prefixLen+1, chars );
      
      //restore the environment after recursive and prepare for next loop;
      chars[i] = curChar;  
      prefix[ prefixLen ] = 0;
      
      preChar = curChar;
    }
  }
  
  protected static void print( char[] chars, int length )
  {
    for( int i=0; i<length; ++i )
    {
      System.out.print( chars[i] );
    }
    System.out.println();
  }
}
